package zuochengyun;

import list.ListNode;

//按照左右半区的方式重新组合单链表
public class ReLinkList {

	public void relocate(ListNode head){
		if(head == null || head.next == null){
			return;
		}
		//slow将会指向中间结点
		ListNode slow = head;
		ListNode fast = head;
		while(fast.next != null && fast.next.next != null){
			fast = fast.next;
			slow = slow.next;
		}
		ListNode left = head;
		ListNode right = slow.next;
		slow.next = null;
		merge(left, right);
	}
	
	public void merge(ListNode left, ListNode right){
		//right结点数可能比left多一个或者相等
		ListNode temp = null;
		while(left.next != null){
			temp = right.next;
			right.next = left.next;
			left.next = right;
			left = right.next;
			right = temp;
		}
		//不管right与left是相等还是多一个
		left.next = right;
	}
}
